The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family Fkn of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph Fkn is at least Ω(kn log(n/k)). Next, we construct a universal graph for Fkn with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for Fkn is Θ(kn log(n/k)) .

A feature for classification of shallowly buried landmine-like objects using a ground penetrating radar (GPR) measurement system is proposed and its performance is evaluated. The feature for classification employed here is a time interval between two pulses reflected from top and bottom sides of landmine-like objects. First, we estimate a time resolution required to detect object thickness from GPR data, and check the actual time resolution through laboratory experiment. Next, we evaluate the classification performance using Monte Carlo simulations from dataset generated by a two-dimensional finite difference time domain (FDTD) method. The results show that good classification performance is achieved even for landmine-like objects buried at shallow depths under rough ground surfaces. Furthermore, we also estimate the effects of ground surface roughness, soil inhomogeneity, and target inclination on the classification performance.

We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.

The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.

It has been known that testing of reversible circuits is relatively easier than conventional irreversible circuits in the sense that few test vectors are needed to cover all stuck-at faults. This paper shows, however, that it is NP-hard to generate a minimum complete test set for stuck-at faults on the wires of a reversible circuit using a polynomial time reduction from 3SAT to the problem. We also show non-trivial lower bounds for the size of a minimum complete test set.

We consider the routing for a multicast in a WDM all-optical network. We prove a min-max theorem on the number of wavelengths necessary for routing a multicast. Based on the min-max theorem, we propose an efficient on-line algorithm for routing a multicast.

We introduce the interval set of a graph G which is a representation of the proper-path-decomposition of G, and show a linear time algorithm to construct an optimal interval set for any tree T. It is shown that a proper-path-decomposition of T with optimal width can be obtained from an optimal interval set of T in O(n log n) time.